A Turing machine is a theoretical computing system, described in 1936 by Alan Turing. A Turing machine that can efficiently simulate any other Turing machine is called a Universal Turing Machine (UTM). The Church-Turing thesis states that any practical computing model has either the equivalent or a subset of the capabilities of a UTM.
A quantum computer is any physical system that harnesses one or more quantum effects to perform a computation. A quantum computer that can efficiently simulate any other quantum computer is called a Universal Quantum Computer (UQC).
In 1981 Richard P. Feynman proposed that quantum computers could be used to solve certain computational problems more efficiently than a UTM and therefore invalidate the Church-Turing thesis. See e.g., Feynman R. P., “Simulating Physics with Computers”, International Journal of Theoretical Physics, Vol. 21 (1982) pp. 467-488. For example, Feynman noted that a quantum computer could be used to simulate certain other quantum systems, allowing exponentially faster calculation of certain properties of the simulated quantum system than is possible using a UTM.
Approaches to Quantum Computation
There are several general approaches to the design and operation of quantum computers. One such approach is the “circuit model” of quantum computation. In this approach, qubits are acted upon by sequences of logical gates that are the compiled representation of an algorithm. Circuit model quantum computers have several serious barriers to practical implementation. In the circuit model, it is required that qubits remain coherent over time periods much longer than the single-gate time. This requirement arises because circuit model quantum computers require operations that are collectively called quantum error correction in order to operate. Quantum error correction cannot be performed without the circuit model quantum computer's qubits being capable of maintaining quantum coherence over time periods on the order of 1,000 times the single-gate time. Much research has been focused on developing qubits with coherence sufficient to form the basic information units of circuit model quantum computers. See e.g., Shor, P. W. “Introduction to Quantum Algorithms”, arXiv.org:quant-ph/0005003 (2001), pp. 1-27. The art is still hampered by an inability to increase the coherence of qubits to acceptable levels for designing and operating practical circuit model quantum computers.
Another approach to quantum computation, involves using the natural physical evolution of a system of coupled quantum systems as a computational system. This approach does not make critical use of quantum gates and circuits. Instead, starting from a known initial Hamiltonian, it relies upon the guided physical evolution of a system of coupled quantum systems wherein the problem to be solved has been encoded in the terms of the system's Hamiltonian, so that the final state of the system of coupled quantum systems contains information relating to the answer to the problem to be solved. This approach does not require long qubit coherence times. Examples of this type of approach include adiabatic quantum computation, cluster-state quantum computation, one-way quantum computation, quantum annealing and classical annealing, and are described, for example, in Farhi, E. et al., “Quantum Adiabatic Evolution Algorithms versus Simulated Annealing”, arXiv.org:quant-ph/0201031 (2002), pp 1-16.
Qubits
As mentioned previously, qubits can be used as fundamental units of information for a quantum computer. As with bits in UTMs, qubits can refer to at least two distinct quantities; a qubit can refer to the actual physical device in which information is stored, and it can also refer to the unit of information itself, abstracted away from its physical device.
Qubits generalize the concept of a classical digital bit. A classical information storage device can encode two discrete states, typically labeled “0” and “1”. Physically these two discrete states are represented by two different and distinguishable physical states of the classical information storage device, such as direction or magnitude of magnetic field, current, or voltage, where the quantity encoding the bit state behaves according to the laws of classical physics. A qubit also contains two discrete physical states, which can also be labeled “0” and “1”. Physically these two discrete states are represented by two different and distinguishable physical states of the quantum information storage device, such as direction or magnitude of magnetic field, current, or voltage, where the quantity encoding the bit state behaves according to the laws of quantum physics. If the physical quantity that stores these states behaves quantum mechanically, the device can additionally be placed in a superposition of 0 and 1. That is, the qubit can exist in both a “0” and “1” state at the same time, and so can perform a computation on both states simultaneously. In general, N qubits can be in a superposition of 2N states. Quantum algorithms make use of the superposition property to speed up some computations.
In standard notation, the basis states of a qubit are referred to as the |0> and |1> states. During quantum computation, the state of a qubit, in general, is a superposition of basis states so that the qubit has a nonzero probability of occupying the |0> basis state and a simultaneous nonzero probability of occupying the |1> basis state. Mathematically, a superposition of basis states means that the overall state of the qubit, which is denoted |Ψ>, has the form |Ω>=a|0>+b|1>, where a and b are coefficients corresponding to the probabilities |a|2 and |b|2, respectively. The coefficients a and b each have real and imaginary components, which allows the phase of the qubit to be characterized. The quantum nature of a qubit is largely derived from its ability to exist in a coherent superposition of basis states and for the state of the qubit to have a phase. A qubit will retain this ability to exist as a coherent superposition of basis states when the qubit is sufficiently isolated from sources of decoherence.
To complete a computation using a qubit, the state of the qubit is measured (i.e., read out). Typically, when a measurement of the qubit is performed, the quantum nature of the qubit is temporarily lost and the superposition of basis states collapses to either the |0> basis state or the |1> basis state and thus regaining its similarity to a conventional bit. The actual state of the qubit after it has collapsed depends on the probabilities |a|2 and |b|2 immediately prior to the readout operation.
Superconducting Qubits
There are many different hardware and software approaches under consideration for use in quantum computers. One hardware approach uses integrated circuits formed of superconducting materials, such as aluminum or niobium. The technologies and processes involved in designing and fabricating superconducting integrated circuits are similar to those used for conventional integrated circuits.
Superconducting qubits are a type of superconducting device that can be included in a superconducting integrated circuit. Superconducting qubits can be separated into several categories depending on the physical property used to encode information. For example, they may be separated into charge, flux and phase devices, as discussed in, for example Makhlin et al., 2001, Reviews of Modern Physics 73, pp. 357-400. Charge devices store and manipulate information in the charge states of the device, where elementary charges consist of pairs of electrons called Cooper pairs. A Cooper pair has a charge of 2e and consists of two electrons bound together by, for example, a phonon interaction. See e.g., Nielsen and Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge (2000), pp. 343-345. Flux devices store information in a variable related to the magnetic flux through some part of the device. Phase devices store information in a variable related to the difference in superconducting phase between two regions of the phase device. Recently, hybrid devices using two or more of charge, flux and phase degrees of freedom have been developed. See e.g., U.S. Pat. No. 6,838,694 and U.S. Patent Application No. 2005-0082519.
Graph Theory
Graphs are an effective way of representing relationships among entities, and are very common in all areas of modern life, including economics, mathematics, natural sciences and social sciences. While some graphs are simply used as a visual aid, others can be used to represent a problem to be solved. In fact, mapping a problem into graph format can sometimes help solve the problem. Instances of such problems can include stock portfolio selection, microwave tower placement, delivery route optimization and other large-scale problems. Two types of problems for which graphs are commonly used are optimization problems and decision problems.
A decision problem is a problem for which there exists a yes or no answer. For example, in the Traveling Salesman Problem (“TSP”), it must be determined whether, given a list of locations, a travel route that visits all locations in the list exactly once exists such that the total distance traveled by the salesman is less than a predetermined distance. Optimization problems are problems for which, given a set of constraints, one or more variables are either maximized or minimized. For example, in the optimization version of the TSP, an optimized travel itinerary must be determined, by minimizing a variable, such as distance or cost, e.g., given a list of locations, the shortest route that visits all locations exactly once must be found. For a large list of locations, problems become complex and require exponentially many computations in order to find the solution in the worst case.
Other examples of problems for which graphs may be helpful include maximum independent set, constraint optimization, factoring, prediction modeling and k-SAT. These problems are abstractions of many real-world problems, such as those found in operations research, financial portfolio selection, scheduling, supply management, circuit design and travel route selection.
Graphs are also used in the field of very large scale integration (VLSI) chip design. Given an electronic circuit with many different elements that need to be wired together in a limited space and with specific design rules to be followed, finding an efficient wiring scheme can be done using graphs. Examples of applying graphical techniques to VLSI design can be found in Shields et al., 2001, Parallel and Distributed Computing and Systems Conference, Anaheim, Calif.; and Heckmann et al., 1991, Proc. 17th Int. Workshop on Graph-Theoretic Concepts in Comp. Sci., pp. 25-35.
In some situations, it may be desirable to transform one graph to another such as by embedding a first (source) graph into a second (target) graph. In the present context, graph embedding may be defined as a particular drawing of a source graph or a collection of vertices and edges connecting some subset of the vertices. Graph drawing applies topology and geometry to derive two- and three-dimensional representations of graphs. Graph drawing is motivated by applications such as VLSI circuit design, social network analysis, cartography and bioinformatics. There can be many permutations of, or ways to draw, a source graph; that is, the number of ways a graph can be embedded depends on the characteristics and rules of the target graph. For example, the target graph may be an infinite two-dimensional architecture with vertices placed at 90° to each other. As shown in FIG. 1A, in grid 102, edges 104 between vertices 106 may be constrained to be in two mutually orthogonal directions (e.g., up-down or left-right). In grid 102 every vertex has a degree of 4 (ignoring boundary vertices), meaning that each vertex except the boundary vertices has four edges connected to it, the edges going only in the directions mentioned above. An alternative target graph is an extended grid (EM) 108, as shown in FIG. 1B, where in addition to horizontal and vertical edges 104, edges 110 cross and extend diagonally (e.g., at) 45° between vertices 106. Every vertex of the extended grid 108 has a degree of 8 (ignoring boundary vertices). One type of graph embedding involves translating an arbitrary graph into a grid system such as grid 102 or extended grid 108.
Graphs that can be embedded can be broken into two types: planar and non-planar. Planar graphs are graphs that can be drawn on a two-dimensional plane such that no two edges intersect, while a non-planar graph is a graph where at least two edges intersect. FIG. 1A is an example of a planar graph, while graph 112 of FIG. 1C is an example of a non-planar graph (known as the complete “K5” graph). In some situations, it may be desirable to embed a planar graph onto a non-planar graph or to make a non-planar graph as planar as possible, i.e., by reducing the number of edge crossings.
One possible way of characterizing graph embeddings is their “efficiency”. For some purposes, an efficiency metric may be defined as the amount of resources (e.g., vertices and edges), area, and/or path or edge lengths used to embed a source graph into a target graph. Under such a definition, an “efficient” graph embedding uses fewer resources, occupies less area, has lower average path lengths, or any combination thereof, than an “inefficient” graph embedding. Other efficiency metrics may include perimeter length, area, utilization (ratio of occupied nodes in target graph to unoccupied nodes), configuration and orientation of edges. Those of skill in the art will appreciate that many other metrics for efficiency may be chosen. Since the same graph can be embedded in more than one way, it is often desirable to find the most efficient embedding possible.
For very small planar graphs, known prior art techniques are available for finding the most efficient graph embedding. However, when the graph has a substantial number of vertices and edges, finding an optimal embedding becomes a complex task. Several techniques have been developed to optimize a graph embedding, such as the graph drawing technique developed by Gutwenger et al., 2002, Lecture Notes in Computer Science 2269, pp. 307-323. The Automated Graph Drawing (AGD) software program described in that publication is capable of mapping and compacting graphs using a variety of different techniques. However, all these techniques rely on the planarization of the original graph, which means the original graph is drawn to have as few, if any, crossings as possible. This comes at the expense of having longer edge lengths and greater surface area, since non-planar graphs are generally more compact.
Other forms of graph embedding are discussed in Mutzel, 2002, Handbook of Applied Optimization, Oxford University Press, New York, 2002, pp. 967-977. Mutzel describes many different methodologies for graph embedding and optimization, but again all concentrate on making the graph as planar as possible. Part of the reason Mutzel desires planarity is that it is aesthetically better. However, in instances where aesthetics is not an important aspect of graph optimization, the techniques outlined by Mutzel would not produce the most efficient graph embedding.
A square lattice is a set of points P arranged in n rows and m columns in a plane such that for all Pi in P, Pi=(x, y), 0≦x≦n, 0≦y≦m,
Given the above, there exists a need in the art for efficient methods, systems and apparatus for graph embedding and applications of graph embedding.